package com.xx.springboot.DataStructure.Array;

import java.util.Arrays;

/**
 * Created by xiaoxiunique on 2018-8-3.
 * @author: xiaoxi
 * @desription: 冒泡排序 以及优化
 */
public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = {1, 345, 6, 234, 47, 456, 34, 24};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * { 1 , 2 , 5 , 3 , 6 , 7 , 8}  --> 等待排序的数组
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第一次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第二次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第三次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第四次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第五次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第六次
     * { 1 , 2 , 3 , 5 , 6 , 7 , 8}  --> 第七次
     * @description:
     * 这是一个特殊的排序数组 可以看出 在第一次排序之后 数组就已经有序,
     * 但是这时循环并不会停止, 还是会接着循环 排序,
     * 这时 我们可以添加一个标志位，当发现数组已经有序的时候 我们就退出循环
     *
     * 普通冒泡排序 添加标志位
     * @param arr
     */
    public static void sort(int[] arr) {
        int temp = 0;
        // 标志数组现在是否有序
        boolean  isSorted = true;

        for (int i = 0; i < arr.length - 1; i++) {

            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    // 当发现数组本次有元素换位  改变标志位
                    isSorted = false;
                }
            }

            if (isSorted)
                break;
        }
    }

}
